import java.util.LinkedList;
import java.util.Queue;

public class Solution538 {

    int sum = 0;

    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.right);
        sum += root.val;
        root.val = sum;
        dfs(root.left);
    }

    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private TreeNode deserialize(String data) {
        if(data.equals("")){
            return null;
        }
        String[] strNodeArr = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(strNodeArr[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int ind = 1;
        while(!q.isEmpty()){
            TreeNode tmpNode = q.poll();
            String leftStr = strNodeArr[ind++];
            String rightStr = strNodeArr[ind++];
            if(!leftStr.equals("null")){
                tmpNode.left = new TreeNode(Integer.valueOf(leftStr));
                q.add(tmpNode.left);
            }
            if(!rightStr.equals("null")){
                tmpNode.right = new TreeNode(Integer.valueOf(rightStr));
                q.add(tmpNode.right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Solution538 s = new Solution538();
        s.convertBST(s.deserialize("4,1,6,0,2,5,7,null,null,null,3,null,null,null,8,null,null,null,null"));
    }
}
